Stern-Brocot Trees
Since I was a child I prided myself on knowing arithmetic. I knew how to add fractions. I knew that 2/3 plus 1/4 is 11/12. Some kids around me were struggling and often summed it up the wrong way by adding numerators and denominators separately and getting 3/7 as a result.
As I grew older I found more reasons to ignore the wrong way. For example, the result of such addition depends on the representation of a fraction, not on the fraction itself, and this was bad.
Oh well. I was growing older, but not wiser. Now mathematicians study this wrong addition of fractions. They call such a sum a mediant of two rational numbers. To avoid the dependency on the representation of fractions, the fractions are assumed to be in the lowest terms.
Let us start with the sequence of fractions: 0/1 and 1/0. This sequence is called the Stern-Brocot sequence of order 0. The Stern-Brocot sequence of order n is generated from the Stern-Brocot sequence of order n − 1 by inserting mediants between consecutive elements of the sequence. For example, the Stern-Brocot sequence of order 2 is 0/1, 1/2, 1/1, 2/1, 1/0.
Where are the trees promised in the title? We can build a portion of this binary tree out of the sequence of order n in the following manner. First, ignore the starting points 0/1 and 1/0. Then assign a vertex to every number in the sequence. After that, connect every mediant to one of the two numbers it was calculated from. More precisely, if a number first appeared in the i-th sequence, its only parent is the number that first appeared in the sequence i−1.
There is beautiful theorem that states that every non-negative rational number appears in the Stern-Brocot sequences. The proof is related to continued fraction. Suppose a rational number r is represented as a continued fraction [a0;a1,a2,…,ak], where ak is assumed to be greater than 1 for uniqueness. Then this number first appears in the Stern-Brocot tree of order a0 + a1 + a2 + … + ak + 1, and its parent is equal [a0;a1,a2,…,ak − 1].
My PRIMES student, Dhroova Ayilam, was working on a project suggested by Prof. James Propp. The goal was to find out what happens if we start with any two rational numbers in lowest terms. Dhroova proved that as with the classical Stern-Brocot trees, any rational number in a given range appears in the tree. His paper Modified Stern-Brocot Sequences is available at the arXiv.
Share:
Leo B.:
What is also good about Stern-Brocot sequences that they are a way to get rational approximations with minimal denominators which is less prone to floating point errors than the straightforward continued fraction method.
9 May 2015, 3:00 am